package base.C06_BinarySearch;

/**
 * Instruction：二分法查找: 非递归实现
 * 数组状况: 无重复元素, 有序.
 * Author：@author MaLi
 */
public class Code01_BinarySearch {
    //定义一个查找方法
    public static int find(int[] arr, int num) {
        //有效性验证
        if (arr == null || arr.length < 1)
            return -1;
        //使用非递归模式实现
        int start = 0;
        int end = arr.length - 1;
        int middle;
        while (start <= end) {
            middle = start + ((end - start) >> 1);
            if (arr[middle] == num) {
                return middle;
            } else if (arr[middle] > num) { //说明中间值在目标值的右边, 我们应该重新确定end值, 排除一半无用值
                end = middle - 1;
            } else {
                start = middle + 1;  //说明中间值在目标值的左边, 我们应该重新确定start值, 排除一半无用值
            }
        }
        return -1;
    }
}
